package leetcode.code0801;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int minSwap(int[] nums1, int[] nums2) {
		int ans = 0;
		int len = nums1.length;
		int[][] dp = new int[len][2];
		// dp[i][0]截止位置i，i位置不交换有序的累计交换次数
		// dp[i][1]截止位置i，i位置交换才有序的累计交换次数
		dp[0][0] = 0;// 0位置前没有数，一定是升序，bu换的累计交换次数就是0
		dp[0][1] = 1;// 0位置前没有数，一定是升序， 换的累计交换次数就是1
		// 题目保证，不升序的连续数，交换会有升序【可前，可后】，如下交换6和3，比交换47，58好
		// xxx 6 4 5
		// yyy 3 7 8
		for (int i = 1; i < len; i++) {
			// [0,4,4,5,9]
			// [0,1,6,8,10]
			if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {// 当前连续的数字是满足升序的
				if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {// 交叉也是升序，前面换不换都行
					int min = Math.min(dp[i - 1][0], dp[i - 1][1]);// 前面换不换都行，要小的
					dp[i][0] = min;// i位置换不换都行，不换不+1
					dp[i][1] = min + 1;// 换得+1
				} else {// 交叉不是升序
					dp[i][0] = dp[i - 1][0];// 不换是满足的，前面不换，后面也不换，满足if
					dp[i][1] = dp[i - 1][1] + 1;// 都换是满足的，前面换，后面也换，满足if
				}
			} else {// 当前连续的数字bu满足升序，i-1位置有可能换了，也有可能没换
//				[0,7,8,10,10,11,12,13,19,18]
//				[4,4,5,7,11,14,15,16,17,20]
				dp[i][0] = dp[i - 1][1];// 前面换，后面不换
				dp[i][1] = dp[i - 1][0] + 1;// 前面不换，这个必须换
			}
		}
		return Math.min(dp[len - 1][0], dp[len - 1][1]);
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1, this.minSwap(HelpDebug.str2array3("[1,3,5,4]"), HelpDebug.str2array3("[1,2,3,7]")));

	}

	@Override
	public void debug2() {
//		[0,4,4,5,9]
//		[0,1,6,8,10]
		HelpDebug.compare(1, this.minSwap(HelpDebug.str2array3("[0,4,4,5,9]"), HelpDebug.str2array3("[0,1,6,8,10]")));

	}

	@Override
	public void debug3() {
//		[0,7,8,10,10,11,12,13,19,18]
//		[4,4,5,7,11,14,15,16,17,20]
		HelpDebug.compare(4, this.minSwap(HelpDebug.str2array3("[0,7,8,10,10,11,12,13,19,18]"),
				HelpDebug.str2array3("[4,4,5,7,11,14,15,16,17,20]")));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug3();
		so.debug1();
		so.debug2();
	}

}
